﻿//1. 二叉树中的最大路径和
//https://www.nowcoder.com/practice/da785ea0f64b442488c125b441a4ba4a?tpId=196&tqId=37050&ru=/exam/oj
//#include <iostream>
//#include <string>
//
////using namespace std;
//
//int main()
//{
//
//	//cout << sizeof(wchar_t) << endl;
//	//cout << sizeof(char16_t) << endl;
//	//cout << sizeof(char32_t) << endl;
//
//	std::string s;
//
//	return 0;
//}

//#include <iostream>
//
//using namespace std;
//
//struct TreeNode 
//{
//	int val;
//	struct TreeNode* left;
//	struct TreeNode* right;
//	TreeNode(int x) : val(x), left(nullptr), right(nullptr) 
//	{}
//	
//};

//class Solution
//{
//public:
//	int ret = -1010;
//	int maxPathSum(TreeNode* root)
//	{
//		dfs(root);
//		return ret;
//	}
//	int dfs(TreeNode* root)
//	{
//		if (root == nullptr) return 0;
//		int l = max(0, dfs(root->left)); // 左⼦树的最⼤单链和
//		int r = max(0, dfs(root->right)); // 右⼦树的最⼤单链和
//		// 经过root的最⼤路径和
//		ret = max(ret, root->val + l + r);
//		return root->val + max(l, r);
//	}
//};


//class Solution
//{
//	int ret = -1010;
//public:
//	int maxPathSum(TreeNode* root)
//	{
//		dfs(root);
//		return ret;
//	}
//
//	int dfs(TreeNode* root)
//	{
//		if (root == nullptr)
//		{
//			return 0;
//		}
//		int l = dfs(root->left);
//		int r = dfs(root->right);
//		ret = max(ret, root->val + r + l);
//		return root->val + max(l, r);
//	}
//};


//2. 排序子序列
// https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471
//#include <iostream>
//
//using namespace std;
//
//const int N = 1e5;
//
//int a[N];
//int n;
//
//int main()
//{
//	cin >> n;
//	for (int i = 0; i < n; i++) cin >> a[i];
//
//	int ret = 0;
//	int i = 0;
//	while (i < n)
//	{
//		if (i == n - 1)
//		{
//			ret++;
//			break;
//		}
//
//		if (a[i] < a[i + 1])
//		{
//			while (i < n && a[i] <= a[i + 1])
//			{
//				i++;
//			}
//			ret++;
//		}
//		else if(a[i] > a[i + 1])
//		{
//			while (i < n && a[i] >= a[i + 1])
//			{
//				i++;
//			}
//			ret++;
//		}
//		else
//		{
//			while (i < n && a[i] == a[i + 1])
//			{
//				i++;
//			}
//		}
//
//		i++;
//	}
//
//	cout << ret << endl;
//	return 0;
//}


//3. 消减整数
//https://ac.nowcoder.com/acm/problem/219038
//#include <iostream>
//
//using namespace std;
//
//int func(int x)
//{
//	int ret = 0;
//	int a = 1;
//	while (x)
//	{
//		x -= a;
//		if (x % (2 * a) == 0)
//		{
//			a *= 2;
//		}
//	}
//	return ret;;
//}
//
//int main()
//{
//	int t; cin >> t;
//	while (t--)
//	{
//		int x; cin >> x;
//		cout << func(x) << endl;
//	}
//
//	return 0;
//}


//4. 最长上升子序列(二)
//https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237?tpId=196&tqId=39285&ru=/exam/oj
//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//class Solution
//{
//public:
//    int LIS(vector<int>& a)
//    {
//        vector<int> v;
//        for (auto it = a.begin(); it != a.end(); it++)
//        {
//            auto pos = lower_bound(v.begin(), v.end(), *it);
//            if (pos == v.end())
//            {
//                v.push_back(*it);
//            }
//            else
//            {
//                *pos = *it;
//            }
//        }
//
//        return v.size();
//    }
//};
